package com.itzmn.newcode.offer;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/15 17:20
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer  把二叉树打印成多行
 *
 *    从上到下打印树，从左至右
 */
public class PrintTreeTopToBottom2 {

    public static void main(String[] args) {

    }

    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {


        //借助队列
        LinkedList<TreeNode> treeNodesodd = new LinkedList<>();
        LinkedList<TreeNode> treeNodeseven = new LinkedList<>();
        boolean isodd = true;
        treeNodesodd.add(pRoot);

        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot==null){
            return arrayLists;
        }
        while (!treeNodesodd.isEmpty() || !treeNodeseven.isEmpty()){
            ArrayList<Integer> integers = new ArrayList<>();
            if (isodd){
                while (!treeNodesodd.isEmpty()){
                    TreeNode remove = treeNodesodd.remove();
                    System.out.println(remove.val);
                    integers.add(remove.val);
                    if (remove.left!=null){

                        treeNodeseven.add(remove.left);
                    }
                    if (remove.right!=null){

                        treeNodeseven.add(remove.right);
                    }
                }
            }else {
                while (!treeNodeseven.isEmpty()){
                    TreeNode remove = treeNodeseven.remove();
                    System.out.println(remove.val);
                    integers.add(remove.val);
                    if (remove.left!=null){
                        treeNodesodd.add(remove.left);
                    }
                    if (remove.right!=null){
                        treeNodesodd.add(remove.right);
                    }
                }
            }

            isodd = !isodd;
            arrayLists.add(integers);
        }
        return arrayLists;
    }


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}
